/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(null == root) {
            return null;
        }
        if(p == root || q == root) {
            return root;
        }
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        if(null != leftNode && null != rightNode) {
            return root;
        }else if(null != leftNode) {
            return leftNode;
        }else {
            return rightNode;
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(null == root) {
            return null;
        }
        Stack<TreeNode> stackp = new Stack<>();
        Stack<TreeNode> stackq = new Stack<>();
        //找到到p的路径
        getPath(root,p,stackp);
        //找到到q的路径
        getPath(root,q,stackq);
        if(stackp.size() > stackq.size()) {
            int tem = stackp.size() - stackq.size();
            while(tem > 0) {
                stackp.pop();
                tem--;
            }
        }else if(stackq.size() > stackp.size()) {
            int tem = stackq.size() - stackp.size();
            while(tem > 0) {
                stackq.pop();
                tem--;
            }
        }
        while(!stackp.empty()&&!stackq.empty()) {
            if(stackp.peek() == stackq.peek()) {
                break;
            }else {
                stackp.pop();
                stackq.pop();
            }
        }
        return stackp.peek();
        
    }
    private boolean getPath(TreeNode root,TreeNode k,Stack stack) {
        if(null == root) {
            return false;
        }
        //如果root是k的话也要放进去,因为如果不放进去如果p就是q的公共祖先的话就会缺失这个结点
        stack.push(root);
        if(root == k) {
            return true;
        }
        boolean left = getPath(root.left,k,stack);
        boolean right = getPath(root.right,k,stack);
        if(left || right) {
            return true;
        }
        stack.pop();
        return false;
    }

}